package tree

type Trie struct {
	isFinished bool
	preNumber  int
	children   map[rune]*Trie
}

func New() Trie {
	return Trie{isFinished: false, children: make(map[rune]*Trie)}
}

func (this *Trie) Insert(word string) {

	parent := this
	for _, ch := range word {
		if child, ok := parent.children[ch]; ok {
			parent = child
		} else {
			newChild := New()
			parent.children[ch] = &newChild
			parent = &newChild
		}
		parent.preNumber++

	}

	parent.isFinished = true
}

func (this *Trie) Search(word string) bool {
	parent := this

	for _, ch := range word {
		if child, ok := parent.children[ch]; ok {
			parent = child
		} else {
			return false
		}
	}

	return parent.isFinished
}

func (this *Trie) StartWith(prefix string) bool {
	parent := this
	for _, ch := range prefix {
		if child, ok := parent.children[ch]; ok {
			parent = child
		} else {
			return false
		}
	}

	return true
}
